package com.yoshino.leetcode.improve40.ninth;

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 思路：找到中间的结点，将后面的结点进行反转，然后判断数值是否都相等
        if (head == null || head.next == null) {
            return true;
        }
        ListNode mid = head, last = head;
        while (last.next != null && last.next.next != null) {
            mid = mid.next;
            last = last.next.next;
        }
        // 后部分结点
        last = mid.next;
        mid.next = null;
        last = reverse(last);
        while (last != null) {
            if (last.val != head.val) {
                return false;
            }
            last = last.next;
            head = head.next;
        }
        return true;
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null, cur = head, temp;
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public Node flatten(Node head) {
        // 将子结点扁平化，先序遍历，先处理子结点
        dfs(head);
        return head;
    }

    private Node dfs(Node head) {
        Node cur = head, last = null;

        while (cur != null) {
            Node next = cur.next;
            if (cur.child != null) {
                // 有子结点
                Node childLast = dfs(cur.child);
                // 改变了结构
                next = cur.next;
                // 子结点带进来
                cur.next = cur.child;
                cur.next.prev = cur;
                // next 是否需要介入，需要 子结点的尾部节点
                if (next != null) {
                    next.prev = childLast;
                    childLast.next = next;
                }
                cur.child = null;
                // 结构改变
                last = childLast;
            } else {
                last = cur;
            }
            cur = next;
        }
        return last;
    }

    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        if (head == null) {
            node.next = node;
            return node;
        }
        if (head.next == head) {
            head.next = node;
            node.next = head;
            return head;
        }
        Node cur = head, next = head.next;
        while (next != head) {
            if (insertVal >= cur.val && insertVal <= next.val) {
                break;
            }
            // 分界点
            if (cur.val > next.val) {
                if (insertVal > cur.val || insertVal < next.val) {
                    break;
                }
            }
            cur = next;
            next = next.next;
        }
        cur.next = node;
        node.next = next;
        return head;
    }
}
